package DataStructure.ArrayLearning.Iterator;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * 实现底层是数组的线性表
 */
public class MyArrayList<E> implements MyList<E> {
    // 最大容量
    private final int MAX_CAPACITY = Integer.MAX_VALUE - 8;

    // 默认初始容量
    private final int DEFAULT_CAPACITY = 10;

    // 底层数组
    private Object[] data;

    // 容器现有元素个数
    private int size;

    public MyArrayList() {
        this.data = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList(int initCapacity) {
        if (initCapacity <= 0 || initCapacity > MAX_CAPACITY)
            throw new IllegalArgumentException("capacity is " + initCapacity);
        this.data = new Object[initCapacity];
    }

    /**
     * 末尾添加元素
     *
     * @param e 待添加元素
     * @return 是否添加成功
     */
    @Override
    public boolean add(E e) {
        if (e == null)
            throw new IllegalArgumentException("element is null");
        ensureCapacity();
        data[size++] = e;
        return true;
    }

    /**
     * 在指定索引处添加元素
     *
     * @param index 指定索引
     * @param e     待添加元素
     * @return 是否添加成功
     */
    @Override
    public boolean add(int index, E e) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("index is " + index);
        if (e == null)
            throw new IllegalArgumentException("element is null");
        ensureCapacity();
        // 将 [index, size-1] 的元素全部后移一位
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
        return true;
    }

    /**
     * 删除第一个出现的指定元素
     *
     * @param e 待删除元素
     * @return 是否删除元素
     */
    @Override
    public boolean remove(E e) {
        if (e == null)
            throw new IllegalArgumentException("element is null");
        int index = find(e);
        if (index != -1) {
            remove(index);
            return true;
        } else {
            return false;
        }
    }

    /**
     * 删除指定索引处的元素
     *
     * @param index 指定索引
     * @return 返回删除的元素
     */
    @Override
    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index = " + index);
        E oldElement = (E) data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        return oldElement;
    }

    /**
     * 判断指定元素是否存在
     *
     * @param e 指定元素
     * @return 存在返回 ture，不存在返回 false
     */
    @Override
    public boolean contains(E e) {
        int index = find(e);
        return index != -1;
    }

    /**
     * 查找指定索引的元素
     *
     * @param index 指定索引
     * @return 返回对应元素
     */
    @Override
    public E get(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index = " + index);
        return (E) data[index];
    }

    /**
     * 替换指定元素
     *
     * @param oldValue 原始值
     * @param newValue 新值
     * @return 是否替换成功
     */
    @Override
    public boolean set(E oldValue, E newValue) {
        if (oldValue == null || newValue == null)
            throw new IllegalArgumentException("element is null");
        int index = find(oldValue);
        if (index != -1) {
            data[index] = newValue;
            return true;
        } else {
            return false;
        }
    }

    /**
     * 替换指定索引处的值
     *
     * @param index    指定索引
     * @param newValue 新值
     * @return 被替换的旧值
     */
    @Override
    public E set(int index, E newValue) {
        if (newValue == null)
            throw new IllegalArgumentException("element is null");
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index = " + index);
        E oldValue = (E) data[index];
        data[index] = newValue;
        return null;
    }

    /**
     * 清空列表
     */
    @Override
    public void clear() {
        size = 0;
        data = null;
    }

    /**
     * 返回指定元素第一次出现的下标
     *
     * @param e 指定元素
     * @return 下标，未找到则返回 -1
     */
    @Override
    public int indexOf(E e) {
        if (e == null)
            throw new IllegalArgumentException("element is null");
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 返回指定元素最后一次出现的下标
     *
     * @param e 指定元素
     * @return 下标，未找到则返回 -1
     */
    @Override
    public int lastIndexOf(E e) {
        if (e == null)
            throw new IllegalArgumentException("element is null");
        for (int i = size - 1; i >= 0; i--) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 判空
     *
     * @return 列表为空时返回 true
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回列表大小
     *
     * @return 列表大小
     */
    @Override
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder ret = new StringBuilder("MyArrayList{");
        for (int i = 0; i < size; i++) {
            if (i != 0) ret.append(", ");
            ret.append(data[i]);
        }
        ret.append("}");
        return ret.toString();
    }

    /**
     * 确保数组有剩余空间
     */
    private void ensureCapacity() {
        if (size == data.length) {
            grow();
        }
    }

    /**
     * 实现数组扩容
     */
    private void grow() {
        Object[] newData = new Object[getNewCapacity()];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    /**
     * 获取扩容后的数组长度
     *
     * @return 新长度值
     */
    private int getNewCapacity() {
        int oldCapacity = data.length;
        // 新长度是旧长度的两倍
        int newCapacity = oldCapacity << 1;
        if (newCapacity < 0 || newCapacity > MAX_CAPACITY) {
            // 新扩容的参数太大了.
            newCapacity = MAX_CAPACITY;
        }
        if (oldCapacity == newCapacity) {
            // 组数只能这么大了
            throw new RuntimeException("array is max");
        }
        return newCapacity;
    }

    /**
     * 查找指定元素第一次出现的位置
     *
     * @param e 指定元素
     * @return 位置索引，未找到返回 -1
     */
    private int find(E e) {
        if (e == null)
            throw new IllegalArgumentException("element is null");
        int index = -1;
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                index = i;
                break;
            }
        }
        return index;
    }


    /**
     * 返回此列表的迭代器
     *
     * @return 此列表的迭代器
     */
    @Override
    public MyIterator<E> iterator() {
        return new MyArrayListIterator(0);
    }

    /**
     * 返回此列表的迭代器，并移动到指定下标之前
     *
     * @param index 指定的索引，表示 next() 所返回的第一个值的索引
     * @return 此列表的迭代器
     */
    @Override
    public MyIterator<E> iterator(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException();
        return new MyArrayListIterator(index);
    }

    private class MyArrayListIterator implements MyIterator<E> {
        int cursor;
        int lastRet = -1;

        MyArrayListIterator(int index) {
            cursor = index;
        }

        /**
         * 将指定元素插入的迭代器所在的位置
         *
         * @param e 指定的元素
         */
        @Override
        public void add(E e) {
            MyArrayList.this.add(cursor, e);
            cursor++;
            lastRet = -1;
        }

        /**
         * 向后是否有下一个待迭代的元素
         *
         * @return 有，返回 true
         */
        @Override
        public boolean hasNext() {
            return cursor < size;
        }

        /**
         * 返回向后的下一个待迭代元素的下标
         *
         * @return 下标，在列表尾则返回列表大小
         */
        @Override
        public int nextIndex() {
            return cursor;
        }

        /**
         * 返回向后的下一个待迭代元素
         *
         * @return 返回的元素
         */
        @Override
        public E next() {
            if (cursor >= size)
                throw new NoSuchElementException();
            lastRet = cursor;
            cursor++;
            return (E) data[lastRet];
        }

        /**
         * 向前是否有下一个待迭代的元素
         *
         * @return 有，返回 true
         */
        @Override
        public boolean hasPrevious() {
            return cursor > 0;
        }

        /**
         * 返回向前的下一个待迭代元素的下标
         *
         * @return 下标，在列表头则返回 -1
         */
        @Override
        public int previousIndex() {
            return cursor - 1;
        }

        /**
         * 返回向前的下一个待迭代元素
         *
         * @return 返回的元素
         */
        @Override
        public E previous() {
            if (cursor <= 0)
                throw new NoSuchElementException();
            lastRet = cursor - 1;
            cursor--;
            return (E) data[lastRet];
        }

        /**
         * 在列表中删除上一个被迭代的元素
         */
        @Override
        public void remove() {
            MyArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
        }

        /**
         * 用指定元素替换上一个被迭代的元素
         */
        @Override
        public void set(E e) {
            MyArrayList.this.set(lastRet, e);
        }
    }
}
